package interview.reversewords;

public class ReverseWords {
	public String run(String sentence) {
		if(sentence == null)
			return null;
		
		if(sentence.trim().length() <= 1)
			return sentence;
		
		sentence = sentence.trim();
		
		char[] sArray = sentence.toCharArray();
		int head, tail;
		head = 0;
		tail = sentence.length() - 1;
		
		// reverse the whole sentence
		char temp;
		while(head < tail) {
			temp = sArray[head];
			sArray[head] = sArray[tail];
			sArray[tail] = temp;
			head++;
			tail--;
		}
		
		int word = 0;
		while(word < sArray.length) {
			head = word;
			while(word < sArray.length && sArray[word] != ' ')
				word++;
			tail = word - 1;
			
			// reverse each word
			while(head < tail) {
				temp = sArray[head];
				sArray[head] = sArray[tail];
				sArray[tail] = temp;
				head++;
				tail--;
			}
			
			while(word < sArray.length && sArray[word] == ' ')
				word++;
		}
		
		return new String(sArray);
	}
}
